package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 101.对称二叉树
 */
public class BiTree08_IsSymmetric {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 2, 3, 4, 4, 3);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList, 0);
        System.out.println(BiTreeUtil.preorderTraversal(root));
        // 是否为对称二叉树
        System.out.println(isSymmetric2(root));
    }

    // 递归
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return compare(root.left, root.right);
    }

    // 思路：递归比较左右两棵树的内侧节点和外侧节点是否相等
    public static boolean compare(TreeNode left, TreeNode right) {
        // 递归出口，两棵树是/不是镜像对称
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // left.val = right.val 递归比较外侧和内侧节点
        boolean compareOuter = compare(left.left, right.right);
        boolean compareInner = compare(left.right, right.left);
        return compareOuter && compareInner;
    }

    // 迭代：层序遍历，注意左右子树节点的入队顺序
    public static boolean isSymmetric2(TreeNode root) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode leftNode = queue.poll();
                TreeNode rightNode = queue.poll();
                if (leftNode == null && rightNode == null) {
                    continue;
                }
                if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                    return false;
                }
                // 左右子树节点镜像入队
                queue.offer(leftNode.left);
                queue.offer(rightNode.right);
                queue.offer(leftNode.right);
                queue.offer(rightNode.left);
            }
        }
        return true;
    }

    /**
     * 【相关题目】
     * 100.相同的树
     * 思路：递归比较左右子树的同一侧是否相同
     */
    public static boolean isSameTree(TreeNode left, TreeNode right) {
        // 递归出口，两棵树相同或不同
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // 递归比较子树的左侧和右侧节点
        boolean isSameLeftTree = isSameTree(left.left, right.left);
        boolean isSameRightTree = isSameTree(left.right, right.right);
        return isSameLeftTree && isSameRightTree;
    }

    public static boolean isSameTree2(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(left);
        queue.offer(right);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode leftNode = queue.poll();
                TreeNode rightNode = queue.poll();
                if (leftNode == null && rightNode == null) {
                    continue;
                }
                if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                    return false;
                }
                // 左右子树节点按顺序入队
                queue.offer(leftNode.left);
                queue.offer(rightNode.left);
                queue.offer(leftNode.right);
                queue.offer(rightNode.right);
            }
        }
        return true;
    }

    /**
     * 572.另一棵树的子树
     * 思路：递归比较左右子树是否相等
     */
    public static boolean isSubTree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return isSameTree(root, subRoot) || isSubTree(root.left, subRoot) || isSubTree(root.right, subRoot);
    }

}
